Solving 10385 - Duathlon (Ternary search)
[andmenj-acm.git] / 11846 - Finding Seats Again / 11846.2.cpp
blobed2ceb6b31106697a5fd0753ad740bc1b0803cd3
1 // Accepted
2 using namespace std;
3 #include <algorithm>
4 #include <iostream>
5 #include <iterator>
6 #include <numeric>
7 #include <sstream>
8 #include <fstream>
9 #include <cassert>
10 #include <climits>
11 #include <cstdlib>
12 #include <cstring>
13 #include <string>
14 #include <cstdio>
15 #include <vector>
16 #include <cmath>
17 #include <queue>
18 #include <deque>
19 #include <stack>
20 #include <list>
21 #include <map>
22 #include <set>
24 #define foreach(x, v) for (typeof (v).begin() x=(v).begin(); x !=(v).end(); ++x)
25 #define For(i, a, b) for (int i=(a); i<(b); ++i)
26 #define D(x) cout << #x " is " << x << endl
28 namespace IO {
29 #define MAXBUFF (1<<18)
30 char inBuffer[MAXBUFF], *pIn = inBuffer+MAXBUFF;
31 char outBuffer[MAXBUFF], *pOut = outBuffer;
33 inline char read_char() {
34 if( pIn == inBuffer+MAXBUFF ) {
35 fread( inBuffer, 1, MAXBUFF, stdin );
36 pIn = inBuffer;
38 return *pIn++;
41 inline int read_int() {
42 char c;
43 while( !isdigit(c = read_char()) );
44 int ret = c-'0';
45 while( isdigit(c = read_char()) ) ret = ret * 10 + c-'0';
46 return ret;
49 void flush() {
50 fwrite( outBuffer, 1, pOut-outBuffer, stdout );
51 pOut = outBuffer;
54 inline void write( char c ) {
55 if( pOut == outBuffer+MAXBUFF ) {
56 fwrite( outBuffer, 1, MAXBUFF, stdout );
57 pOut = outBuffer;
59 *pOut++ = c;
63 const int MAXN = 20;
64 const int MAXK = 26;
66 struct region {
67 short r1, r2, c1, c2;
68 region() {}
69 region(short r1, short r2, short c1, short c2) : r1(r1), r2(r2), c1(c1), c2(c2) {}
72 int N, K;
73 char mat[MAXN+1][MAXN+1];
74 region regions[MAXK * 32];
75 int totalRegions;
77 inline void fillRegion(const region &r, char letter) {
78 for (int i = r.r1; i <= r.r2; ++i) {
79 for (int j = r.c1; j <= r.c2; ++j) {
80 mat[i][j] = letter;
85 inline bool isEmpty(const region &r) {
86 for (int i = r.r1; i <= r.r2; ++i) {
87 for (int j = r.c1; j <= r.c2; ++j) {
88 if (mat[i][j] != '.') return false;
91 return true;
94 bool backtrack(int cell, char face) {
95 int r = cell / N;
96 int c = cell % N;
98 if (r >= N or c >= N) {
99 for (int i = 0; i < N; ++i) {
100 for (int j = 0; j < N; ++j) {
101 IO::write(mat[i][j]);
103 IO::write('\n');
105 return true;
108 if (mat[r][c] != '.') return backtrack(cell + 1, face);
110 for (int k = 0; k < totalRegions; ++k) {
111 const region &rg = regions[k];
112 if (r != rg.r1 or c != rg.c1) continue;
113 if (!isEmpty(rg)) continue;
114 fillRegion(rg, face);
115 if (backtrack(cell + 1, face + 1)) return true;
116 fillRegion(rg, '.');
118 return false;
121 int main(){
122 while (true) {
123 N = IO::read_int();
124 K = IO::read_int();
125 if (N == 0 and K == 0) break;
127 for (int i = 0; i < N; ++i) {
128 for (int j = 0; j < N; ++j) {
129 char c = IO::read_char(); while (isspace(c)) c = IO::read_char();
130 mat[i][j] = c;
134 totalRegions = 0;
136 for (int i = 0; i < N; ++i) {
137 for (int j = 0; j < N; ++j) {
138 if (mat[i][j] == '.') continue;
139 int size = mat[i][j] - '0';
140 mat[i][j] = '.';
141 for (int width = 1; width <= size; ++width) {
142 if (size % width != 0) continue;
143 int height = size / width;
144 for (int ii = max(0, i - height + 1); ii + height - 1 < N and ii <= i; ++ii) {
145 for (int jj = max(0, j - width + 1); jj + width - 1 < N and jj <= j; ++jj) {
146 region r(ii, ii + height - 1, jj, jj + width - 1);
147 if (isEmpty(r)) {
148 regions[totalRegions++] = r;
153 mat[i][j] = '0' + size;
157 for (int i = 0; i < N; ++i) {
158 for (int j = 0; j < N; ++j) {
159 mat[i][j] = '.';
162 backtrack(0, 'A');
164 IO::flush();
165 return 0;